package Data_Structure.Sort;

/**
 * @className: SelectSort
 * @author: 芃
 * @description: 选择排序实现
 * @date: 2023/8/20 17:19
 */
//主要思想：
//从i=0下标开始遍历数组，从i+1位置开始找比arr[i]小的元素
//如果小于arr[i]位置的元素，则交换两个下标的元素
//优化：每趟遍历时，遍历完成后找出最小的元素并记录其下标，和arr[i]进行比较，如果小于，则交换即可，减少了不必要的交换

//时间复杂度：O(N^2)
//空间复杂度：O(1)
//稳定性：不稳定的排序
public class SelectSort {
    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int min = Integer.MAX_VALUE;
            int index = -1;
            //找出每一趟当中的最小值
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j] < min){
                    min = arr[j];
                    index = j;
                }
            }
            //取最小值和arr[i]比较，如果小，就交换
            if (arr[i] > min){
                int tmp = arr[i];
                arr[i] = min;
                arr[index] = tmp;
            }
        }
    }
}
